package com.ljx.SlidingWindow;

import java.util.HashMap;

/**
 * @author 李加喜
 * @Package com.ljx.SlidingWindow
 * @date 2021-11-09 20:50
 */
// 最小覆盖子串
public class ZiChuan {
    public static void main(String[] args) {
        String s = "ACDREA";
        String t = "AA";
        ZiChuan ziChuan = new ZiChuan();
        System.out.println(ziChuan.minWindow(s, t));
    }
    /* 滑动窗口算法框架 */
//    void slidingWindow(string s, string t) {
//        unordered_map<char, int> need, window;
//        for (char c : t) need[c]++;
//
//        int left = 0, right = 0;
//        int valid = 0;
//        while (right < s.size()) {
//            // c 是将移入窗口的字符
//            char c = s[right];
//            // 右移窗口
//            right++;
//            // 进行窗口内数据的一系列更新
//        ...
//
//            /*** debug 输出的位置 ***/
//            printf("window: [%d, %d)\n", left, right);
//            /********************/
//
//            // 判断左侧窗口是否要收缩
//            while (window needs shrink) {
//                // d 是将移出窗口的字符
//                char d = s[left];
//                // 左移窗口
//                left++;
//                // 进行窗口内数据的一系列更新
//            ...
//            }
//        }
//    }
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<Character, Integer>(16);
        HashMap<Character, Integer> window = new HashMap<>(16);
        char[] ts = t.toCharArray();
        for (char tss : ts) {
            need.put(tss, need.getOrDefault(tss, 0) + 1);
        }
        int left = 0, right = 0;
        // 记录的是滑动窗口的数量
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        char[] sList = s.toCharArray();
        while (right < sList.length) {
            // 准备放入到窗口的字符
            char c = sList[right];
            // 右移窗口
            right++;
            // 更新窗口的数据
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 判断左侧的窗口是否需要进行收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // 取出要移除窗口的字符
                char d = sList[left];
                // 左移窗口
                left++;
                // 对窗口内的数据进行更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ?
                "" : s.substring(start, start+len);
    }
}
